This invention relates to an image processing system and an image processing method and in particular to an image processing system and its control method for coding and decoding image data efficiently.
In recent years, a digital copier for reading an original image through an image input unit such as a scanner, digitally processing obtained image data, and outputting the result through an image output unit such as a printer, thereby making a hard copy of the original has become pervasive.
The digital copier has an electronic sorter function of storing image data corresponding to a number of images in the copier and sorting originals and an electronic RDH function of filing, page editing, etc., as indispensable functions.
Thus, the digital copier contains memory for temporarily storing image data and a data storage unit such as a large-capacity storage unit typified by a hard disk drive and provides the above-mentioned functions by storing image data and performing processing as required.
To store a large amount of image data, the storage capacity of a data storage unit needs to be increased, but the data storage unit also increases in scale and cost with an increase in the data capacity.
To avoid this problem, a large number of methods for compressing image data and storing the compressed data in a data storage unit are proposed.
Resultantly, a data storage unit having a small capacity can store a large amount of image data.
A laser beam printer using a laser beam is known as an image output unit.
Generally, a page description language is used for a control method of image output to the laser beam printer.
More particularly, a host computer transfers the page description language contents describing text information and image information of the output contents to the laser beam printer instead of transferring the output contents to the printer as a bit map image (raster image). When receiving the page description language, the printer interprets the language contents, expands page image data as a bit map image (raster image), and transfers and outputs the image onto paper.
The printer must contain a function of interpreting the page description language contents and memory for retaining bit map image for expanding image data.
For example, with a monochrome printer using A3-size paper for output, the memory capacity becomes 32 Mbytes when the image output resolution is 400 dpi and output gradation is 256 levels of gray.
Further, since a color printer needs to output four colors of Y, M, C, and K, the memory capacity also becomes four times that of the monochrome printer; when the image output resolution is 400 dpi and output gradation is 256 levels of gray, the memory capacity becomes 128 Mbytes.
Installation of such large-capacity memory in the printer leads to an increase in the scale and cost of the printer; it is not preferred.
Then, to avoid the problem, a method of compressing image data for decreasing the necessary memory capacity is proposed.
To compress image data for decreasing the data capacity, if the number of gradation steps for reproducing an image is decreased, the finally provided image output quality is degraded. The effect is large particularly if an image is stored in a binarized state.
Thus, to provide high-quality image output, it is desirable to store an image in a multiple-valued state.
A large number of methods of compressing multiple-valued image data are available.
A text area and a photo area often are mixed even in a 1-sheet original among originals output to a digital copier or a printer.
A computer-prepared image, so-called computer graphics (CG) image, and a scanned image of a photo, etc., read through a scanner often are mixed in a printer output image.
The CG and scanned images have entirely different image characteristics.
For example, a CG image area in which a CG image is drawn is constant in pixel value change and contains a flat background area with no pixel image change as a large part.
However, the CG image area also contains a text area containing only binary values of monochrome, a gradation area in which pixel values change violently, and the like.
In contrast, a scanned image area in which a scanned image is drawn often contains noise when the image is read through the scanner; pixel values often change finely even in an area which seems to be flat, such as an image background or blank.
Since the CG image and scanned image areas have different image characteristics, proper compression processing to the image characteristics in each of the CG image and scanned image areas needs to be performed to suppress image quality degradation and effectively compress the image data corresponding to an image having mixed CG image and scanned image areas.
To meet such demand, it is necessary to select optimum image processing for each area of the image data corresponding to an image having mixed areas having different image characteristics in response to the image characteristic and perform compression processing accordingly.
A large number of compression techniques for performing optimum image processing for each area are proposed as adaptive image compression technique or multi-mode compression technique.
Since the CG image area often contains an image requiring a high resolution, such as a text or a line drawing, a compression technique suppressing resolution data degradation is desired for the CG image area.
For example, a reversible compression technique of MMR (Modified Read), LZW (Lempel-Ziv-Welch), JBIG (Joint Bi-level Image Group), etc., or a block compression technique of block truncation coding, etc., wherein resolution data is not degraded although gradation data is degraded is appropriate for the CG image area.
Block run length coding of dividing an image into blocks each consisting of n.times.m pixels and combining the representative value of the block and the number of the continuous blocks having the value is appropriate for a background area with little pixel value change in the CG image area.
Since the scanned image area often contains an image requiring the number of gradation steps rather than resolution, such as a photo or a natural image, a compression technique suppressing gradation data degradation is desired for the scanned image area.
By the way, if the reversible compression technique suppressing image degradation after decompression is applied to the scanned image area, pixel values change violently and entropy is high in the scanned image area, thus the compression efficiency cannot be enhanced in the reversible compression technique.
Then, an irreversible technique capable of retaining gradation data corresponding to the number of gradation steps after decompression is desired for the scanned image area.
For example, ADCT (Adaptive Discrete Cosine Transform), etc., typified by JPEG (Joint Photographic Experts Group) baseline technique adopted as a color fax standardization technique is appropriate for the scanned image area.
The block truncation coding will be discussed.
The block truncation coding is one type of block coding for dividing an image into blocks each consisting of m.times.n (m and n are natural numbers except m=n=1) pixels, calculating one or more values representing a block for each block, which will be hereinafter referred to as block representative value or values, and to calculate more than one block representative value, determining index numbers indicating which block representative value is assigned to each pixel in the block.
The block truncation coding is a coding technique using block representative values and the index number assigned to each pixel as code data and the provided code data amount and decoded image quality are determined according to the number of block representative values.
A: When the Number of Block Representative Values is One
When the number of block representative values is one, for example, the mean value, etc., in the block is used as the block representative value and is assigned to all pixels in the block.
Resultantly, in the decoded image, the entire block becomes the one color corresponding to the block representative value assigned.
B: When the Number of Block Representative Values is Two
When the number of block representative values is two, for example, the maximum and minimum values of the pixel data of the pixels making up the block are used as the block representative values. Which of the two block representative values each pixel in the block is more closely analogous to is determined, and the index number corresponding to the block representative value more closely analogous to each pixel is assigned thereto.
More specifically, the index numbers assigned to the pixels representing the two block representative values can be represented in one bit and thus assuming that an image is divided into blocks each consisting of 4.times.4 pixels and that each of the two block representative values is represented in eight bits equal to the number of gradation data bits of the original image, the code amount required for representing each block, M, is ##EQU1##
The original image data amount M' is ##EQU2## ##EQU3##
C: When the Number of Block Representative Values is Four
When the number of block representative values is four, generally the block representative values are calculated based on the maximum value, the minimum value, the dynamic range, the mean value, etc., of the pixel data of the pixels making up the block. Which of the four block representative values each pixel in the block is more closely analogous to is determined, and the index number corresponding to the block representative value more closely analogous to each pixel is assigned thereto.
More specifically, the index numbers assigned to the pixels representing the four block representative values can be represented in two bits and thus assuming that an image is divided into blocks each consisting of 4.times.4 pixels and that each of the four block representative values is represented in eight bits equal to the number of gradation data bits of the original image, the code amount required for representing each block, M, is ##EQU4##
The original image data amount M' is ##EQU5## ##EQU6##
In the block truncation coding, the block size (=m.times.n) can be set to any size.
However, in the block truncation coding, the pixel values contained in the block are approximated by a limited number of block representative values, thus if the block size is large and the number of block representative values is small, the difference between the decoded image and the original image grows.
If the number of block representative values is increased to avoid this problem, the number of bits of data indicating the index number representing the block representative value assigned to each pixel increases and the compression efficiency lowers.
Therefore, generally the block truncation coding is executed in a block size of about 4.times.4 pixels.
The multi-mode compression technique using the block truncation coding and ADCT coding in combination will be discussed.
The multi-mode compression technique using the block truncation coding and ADCT coding in combination requires that the block truncation coding and ADCT coding be changed in block units.
In the two coding techniques, coding processing is performed in block units; to change the coding technique in block units, the block size needs to be made common to the two coding techniques.
The block size in the ADCT coding generally is 8.times.8 pixels. In the ADCT coding, a block size smaller than the block size of 8.times.8 pixels can be adopted theoretically, but the number of DCT coefficients generated at the DCT (Discrete Cosine Transform) operation time decreases extremely, thus effective coding cannot be executed and a block size smaller than that of 8.times.8 pixels is not practical.
Therefore, preferably the block size in the multi-mode compression technique is also set to 8.times.8 pixels and the block size in the block truncation coding is also set to 8.times.8 pixels inevitably.
To code image data of an image having mixed CG image and scanned image areas according to the multi-mode compression technique, the blocks where image data is to be coded-can be classified into the following three types according to the type of image contained therein:
(1) Block containing only a CG image area; PA1 (2) Block containing only a scanned image area; and PA1 (3) Block containing both CG image and scanned image areas
It is desirable to code the block containing only a CG image area by executing the block truncation coding and the block containing only a scanned image area by executing the ADCT coding as described above.
By the way, if the block containing both CG image and scanned image areas is coded by executing the ADCT coding, it is feared that mosquito noise, which is noise proper to the ADCT coding, may become obtrusive in the CG image area in the proximity of the boundary between the CG image and scanned image areas, degrading the decomposed image quality. Therefore, it is desirable to code the block containing both CG image and scanned image areas by executing the block truncation coding; the block size becomes 8.times.8 pixels as described above.
To execute the block truncation coding in a block of 8.times.8 pixels, at least four block representative values need to be set. Therefore, generally the block representative values are calculated based on the maximum value, the minimum value, the dynamic range, the mean value, etc., of the pixel data of the pixels making up the block, as described above.
However, the block representative value determining method as linear operation assumes image data having a histogram distribution in which the pixel values of the pixels making up the image data to be coded are comparatively smooth and continuous, for example, as in a scanned image area.
Therefore, if a discrete distribution and a smooth and continuous distribution are mixed as a pixel value distribution as in the block containing both CG image and scanned image areas, the block representative value determining method as linear operation is difficult to determine effective block representative values.
More specifically, the CG image area often contains constant pixel values continuous in a small area.
Thus, when a small area in which the same pixel values are continuous is divided into blocks and the block truncation coding is executed in the blocks, if the blocks differ in block representative values, a decomposed image becomes very unnatural, degrading the image quality.
However, since the block representative values are determined as linear operation in the conventional block truncation coding, the above-described problem occurs in the CG image area and a high-quality decomposed image cannot be provided.